package com.heihei.demo04;

/**
 *  寻找两个正序数组的中位数
 *
 * @version 1.0
 * @since JDK1.8
 * @author duanhengfei
 * @date 2021年03月02日 09:46:56
 */
public class MedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 3};
        int[] nums2 = new int[]{2};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }

    /**
     * 方法描述: 方法一  自己手写的
     * 耗时 3ms， 击败 82.27 %
     * 内存 39.8MB，  击败  47.94%
     *
     * @param nums1
     * @param nums2
     * @Return {@link double}
     * @throws
     * @author duanhengfei
     * @date 2021年03月02日 10:45:00
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int index = 1;
        int sumLength = nums1.length + nums2.length;
        //如果两个数组都为空，则返回-1
        if(sumLength == -1) {
            return -1;
        }
        //如果一个为空，另一个数组只有一个原色，则返回这个元素
        if(sumLength == 1) {
            return nums1.length == 0 ? nums2[0] : nums1[0];
        }
        //计算中位数是第几个数（如果总数基数个，则中位数取中间那个数；  如果总数偶数个，那就获取到中间两个的前一个的索引）
        int targetIndex = sumLength % 2 == 1 ? sumLength / 2 + 1 : sumLength / 2;
        int nextNum = 0;
        int zhongweishu = 0;
        //循环结束后：  zhongweishu存储目标索引的数值，nextNum存储下一个的数值
        //注：sumLength为基数个，那中位数就是 zhongweishu；    如果sumLength为偶数个，中位数为zhognweishu和nextNum的平均值
        for (int i = 0, j = 0; i < nums1.length || j < nums2.length; ) {
            if(i >= nums1.length) {
                zhongweishu = nextNum;
                nextNum = nums2[j++];
                if(index == targetIndex + 1) {
                    break;
                }
                index++;
                continue;
            }
            if(j >= nums2.length) {
                zhongweishu = nextNum;
                nextNum = nums1[i++];
                if(index == targetIndex + 1) {
                    break;
                }
                index++;
                continue;
            }
            if(nums1[i] < nums2[j]) {
                zhongweishu = nextNum;
                nextNum = nums1[i++];
            } else {
                zhongweishu = nextNum;
                nextNum = nums2[j++];
            }
            if(index == targetIndex + 1) {
                break;
            }
            index++;
        }
        return sumLength % 2 == 1 ? zhongweishu : (zhongweishu + nextNum) / 2D;
    }
}